const Comparator = require('../utils/Comparator');
module.exports = class Heap {
  constructor(comparatorFunction) {
    if (new.target === Heap) {
      throw new TypeError('不能直接创建Heap实例');
    }
    this.heapContainer = [];
    // 比较器，默认使用utils/Comparator.js下的static defaultCompareFunction
    this.compare = new Comparator(comparatorFunction);
  }
  // 获取左侧子节点对应的索引
  getLeftChildIndex(parentIndex) {
    return 2 * parentIndex + 1;
  }
  // 获取右侧子节点对应的索引
  getRightChildIndex(parentIndex) {
    return 2 * parentIndex + 2;
  }
  // 获取父节点对应的索引
  getParentIndex(childIndex) {
    return Math.floor((childIndex - 1) / 2);
  }
  // 是否有父节点，除了根节点，其余节点都应该有父节点
  hasParent(childIndex) {
    return this.getLeftChildIndex(childIndex) >= 0;
  }
  // 是否有左侧子节点
  hasLeftChild(parentIndex) {
    return this.getLeftChildIndex(parentIndex) < this.heapContainer.length;
  }
  // 是否有右侧子节点
  hasRightChild(parentIndex) {
    return this.getRightChildIndex(parentIndex) < this.heapContainer.length;
  }
  // 左侧子节点
  leftChild(parentIndex) {
    return this.heapContainer[this.getLeftChildIndex(parentIndex)];
  }
  // 右侧子节点
  rightChild(parentIndex) {
    return this.heapContainer[this.getRightChildIndex(parentIndex)];
  }
  // 父节点
  parent(childIndex) {
    return this.heapContainer[this.getParentIndex(childIndex)];
  }
  // 交换两个节点
  swap(indexOne, indexTwo) {
    const tmp = this.heapContainer[indexTwo];
    this.heapContainer[indexTwo] = this.heapContainer[indexOne];
    this.heapContainer[indexOne] = tmp;
  }
  // 根节点
  peek() {
    if (this.heapContainer.length === 0) {
      return null;
    }
    return this.heapContainer[0];
  }
  // 轮询节点
  poll() {
    if (this.heapContainer.length === 0) {
      return null;
    }

    if (this.heapContainer.length === 1) {
      return this.heapContainer.pop();
    }
    // 轮询是自上往下的，轮询完当前节点之后，需要删除节点，那么就会把堆最后的节点放到堆的根节点，同时删除堆最后的节点，然后对堆的根节点进行下降，保证原本堆的特征，例如：最大堆或者最小堆
    const item = this.heapContainer[0];

    this.heapContainer[0] = this.heapContainer.pop();
    this.heapifyDown();

    return item;
  }
  // 添加节点
  add(item) {
    // 直接将节点放入堆的末尾，并对末尾节点进行堆上升或者下降，从而保证堆的特征，例如：最大堆或者最小堆
    this.heapContainer.push(item);
    this.heapifyUp();
    return this;
  }
  // 删除节点
  remove(item, comparator = this.compare) {
    // 获取到节点对应的索引
    const numberOfItemsToRemove = this.find(item, comparator).length;

    for (let iteration = 0; iteration < numberOfItemsToRemove; iteration += 1) {
      const indexToRemove = this.find(item, comparator).pop();

      if (indexToRemove === this.heapContainer.length - 1) {
        // 如果当前索引刚好是堆的最后节点，直接删除，不用再对堆进行排序了
        this.heapContainer.pop();
      } else {
        // 将当前节点替换为堆的最后节点，同时删除堆的最后节点，最终通过对堆的上升或者下降来保持堆原本的特征，例如：最大堆或者最小堆
        this.heapContainer[indexToRemove] = this.heapContainer.pop();

        const parentItem = this.parent(indexToRemove);
        // 如果要删除的节点存在左子节点，并且如果这个节点是根节点或者满足父节点和被替换后节点的比较关系，就进行当前节点堆的下降；否则进行当前节点堆的上升
        if (
          this.hasLeftChild(indexToRemove) &&
          (!parentItem ||
            this.pairIsInCorrectOrder(
              parentItem,
              this.heapContainer[indexToRemove]
            ))
        ) {
          this.heapifyDown(indexToRemove);
        } else {
          this.heapifyUp(indexToRemove);
        }
      }
    }
    return this;
  }
  // 查询满足对应comparator的节点，返回节点对应的索引
  find(item, comparator = this.compare) {
    return this.heapContainer.reduce((acc, cur, index) => {
      if (comparator.equal(cur, item)) {
        acc.push(index);
      }
    }, []);
  }
  isEmpty() {
    return !this.heapContainer.length;
  }
  toString() {
    return this.heapContainer.toString();
  }
  // 对应节点堆上升
  heapifyUp(customStartIndex) {
    let currentIndex = customStartIndex || this.heapContainer.length - 1;

    while (
      this.hasParent(currentIndex) &&
      !this.pairIsInCorrectOrder(
        this.parent(currentIndex),
        this.heapContainer[currentIndex]
      )
    ) {
      this.swap(currentIndex, this.getParentIndex(currentIndex));
      currentIndex = this.getParentIndex(currentIndex);
    }
  }
  // 对应节点堆下降
  heapifyDown(customStartIndex = 0) {
    let currentIndex = customStartIndex;
    let nextIndex = null;

    while (this.hasLeftChild(currentIndex)) {
      if (
        this.hasRightChild(currentIndex) &&
        this.pairIsInCorrectOrder(
          this.rightChild(currentIndex),
          this.leftChild(currentIndex)
        )
      ) {
        nextIndex = this.getRightChildIndex(currentIndex);
      } else {
        nextIndex = this.getLeftChildIndex(currentIndex);
      }

      if (
        this.pairIsInCorrectOrder(
          this.heapContainer[currentIndex],
          this.heapContainer[nextIndex]
        )
      ) {
        break;
      }

      this.swap(currentIndex, nextIndex);

      currentIndex = nextIndex;
    }
  }
  // 抽象方法，需要自身实现方法来比较两个堆对的比较，例如：如果实现
  // 最大堆，那么firstElement >= secondElement；实现最小堆，那么
  // firstElement <= secondElement
  pairIsInCorrectOrder(firstElement, secondElement) {
    throw new Error(
      '你必须实现一个pairIsInCorrectOrder方法，来比较堆对 ' +
        firstElement +
        ' 和 ' +
        secondElement +
        ' 的比较'
    );
  }
};
